package com.yuw.sort;

public class BinarySearchTestDriver {

	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
		System.out.println("查找结果：" + binarySearch(arr, 0, arr.length - 1, 15));
	}

	/**
	 * 二分查找算法【前提条件，必须是有序序列】【相等判定】
	 * 
	 * @param arr       被查找的数组
	 * @param searchVal 被查找的值
	 * @param begin     查找范围的开始下标
	 * @param end       查找范围的结束下标
	 * @return 找到的下标位置，-1表示没有找到
	 */
	public static int binarySearch(int[] arr, int begin, int end, int searchVal) {
		// 返回值，默认为-1，表示没有找到
		int index = -1;
		// 结束条件:没有找到
		if (begin > end) {
			// 没有找到，递归结束
			return index;
		}

		// 取出中间元素
		int mid = (begin + end) / 2;
		// 取出中间元素的值
		int midVal = arr[mid];
		// 结束条件：找到了
		if (searchVal == midVal) {
			// 找到了，返回找到的位置
			return mid;
		} else if (searchVal > midVal) {
			// 继续递归调用, 递归右半部分
			return binarySearch(arr, mid + 1, end, searchVal);
		} else {
			// 继续递归调用,递归左半部分
			return binarySearch(arr, begin, mid - 1, searchVal);
		}
	}

}
